#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

//int t, n, m;
//int cnt[11];
//struct node {
//	int val, id;
//};
//bool check(int x) {
//	for (int i = x + 1; i <= 9; i++)
//		if (cnt[i])return 0;
//	return 1;
//}
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> t;
//	while (t--) {
//		cin >> n >> m;
//		queue<node> ok;
//		int ans = 0;
//		for (int i = 1; i <= 9; i++)
//		{
//			cnt[i] = 0;
//		}
//		for (int i = 1; i <= n; i++)
//		{
//			node tmp;
//			cin >> tmp.val, tmp.id = i - 1;
//			ok.push(tmp);
//			cnt[tmp.val]++;
//		}
//		while (!ok.empty()) {
//			node h = ok.front();
//			ok.pop();
//			if (check(h.val)) {
//				ans++, cnt[h.val]--;
//				if (h.id == m)
//					cout << ans << '\n';
//			}
//			else ok.push(h);
//		}
//	}
//	return 0;
//}

//int t,n;
//vector<pair<int, int>>ok;
//bool cmp(pair<int ,int >a,pair<int , int>b) {
//	if (a.first > b.first) return 1;
//	if (a.first == b.first && a.second < b.second)return 1;
//	return 0;
//}
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> t;
//	while (t--) {
//		cin >> n;
//		ok.clear();
//		for (int i = 1; i <= n; i++)
//		{
//			int x, y;
//			cin >> x >> y;
//			ok.push_back({ x,y });
//		}
//		sort(ok.begin(), ok.end(), cmp);
//		for (int i = ok.size()-1; i >= 0; i--)
//		{
//			cout << ok[i].first << ' ' << ok[i].second;
//			cout << '\n';
//		}
//	}
//	return 0;
//}


//int t, n;
//string s[100005];
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> t;
//    while (t--) {
//        cin >> n;
//        getline(cin, s[0]);
//        for (int i = 1; i <= n; i++)
//        {
//            getline(cin, s[i]);
//        }
//        sort(s + 1, s + n + 1);
//        s[n + 1] = "";
//        int c = 1;
//        for (int i = 1; i <= n; i++)
//        {
//
//            if (s[i + 1].compare(s[i]) == 0)
//            {
//                c++;
//            }
//            else
//            {
//                cout << s[i] << ' ' << c << '\n';
//                c = 1;
//            }
//        }
//    }
//	return 0;
//}